POI2008 Robinson

POI
BFS, 差分前缀和

POI2008 Robinson

题目大意：

给出一个地图，上面有水，还有一些点不能抵达。你要开着船从水上走出这个地图，而不使船碰到不能抵达的点。问最少要多少步。(可能无解)

( $ 3 \le n \le 2000$ )

题解：

求最少步数，用广搜是比较显然的。

我们定义船最长的一行和最长的一列的交点为船的中心。

那么重点就在于处理船可以将中心移动到那些点上。

首先我们枚举一个点$(x,y)$，找到该点向上走到达的第一个不可抵达的点，由此可以算出一个船在x这一行左右移动，一个不可行的区间。同理，向下走找到第一个不可抵达的点，也可得到一个不可行的区间。

同理，我们也可以用这种方法求，一个船在y这一列上下移动，若干个不可行的区间。

对于这些区间，我们可以直接用差分前缀和维护，从而$O(n^2)$预处理出每一个点是否可行。

之后再广搜。

还有一个值得注意的地方，那就是当中心移到边缘时，船还不算出去了，还要把整个船身都移出去才可以。

这可以通过船所在的边缘，直接预处理出代价。

另外，如果船的中心从图的一个角出去，代价需要另外预处理。

综上，总的时间复杂度为$O(n^2)$。

说起来比较容易，但敲起来比较痛。随便敲一下就200+了，又调试了半天，总算解决了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include<queue>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2002,inf=1<<30;
void Min(int&a,int b){
	if(b<a)a=b;
}
void Max(int&a,int b){
	if(b>a)a=b;
}
char str[N][N];
int n,xu,xd,yl,yr,xm,ym;
int ul[N],ur[N],dl[N],dr[N];
int up[N],dw[N],sum[N][N];
bool cov[N][N];
struct node{
	int x,y,step;
};
queue<node>que;
int rx[]={0,1,0,-1};
int ry[]={1,0,-1,0};
bool used[N][N];
bool judge(int x,int y){//该点能否到达
	if(x<=0||x>n||y<=0||y>n||cov[x][y]||used[x][y])return false;
	return true;
}
int ans,step11,step1n,stepn1,stepnn;
void check_ans(int x,int y,int step){
  	//从边缘出去
	if(x==1)Min(ans,step+xd-xm+1);
	if(x==n)Min(ans,step+xm-xu+1);
	if(y==1)Min(ans,step+yr-ym+1);
	if(y==n)Min(ans,step+ym-yl+1);
	//从角落出去
  	if(x==1&&y==1)Min(ans,step+step11);
	if(x==1&&y==n)Min(ans,step+step1n);
	if(x==n&&y==1)Min(ans,step+stepn1);
	if(x==n&&y==n)Min(ans,step+stepnn);
}
int BFS(){//广搜
	ans=inf;
	while(!que.empty())que.pop();
	used[xm][ym]=true;
	que.push((node){xm,ym,0});
	check_ans(xm,ym,0);
	while(!que.empty()){
		node cur=que.front();
		que.pop();
		int px=cur.x,py=cur.y,pstep=cur.step;
		for(int i=0;i<4;i++){
			int nx=px+rx[i],ny=py+ry[i],nstep=pstep+1;
			if(judge(nx,ny)){
				used[nx][ny]=true;
				check_ans(nx,ny,nstep);
				que.push((node){nx,ny,nstep});
			}
		}
	}
	if(ans!=inf)printf("%d\n",ans);
	else printf("NIE\n");
	return 0;
}
int main(){
	scanf("%d",&n);
	xu=yl=inf,xd=yr=0;
	for(int i=1;i<=n;i++){
		scanf("%s",str[i]+1);
		for(int j=1;j<=n;j++){
			if(str[i][j]=='r'){
				Min(xu,i),Max(xd,i);
				Min(yl,j),Max(yr,j);
			}
		}
	}
	for(int i=xu;i<=xd;i++){
		int cnt=0;
		for(int j=yl;j<=yr;j++){
			if(str[i][j]=='r')cnt++;
		}
		if(cnt==yr-yl+1)xm=i;
	}
	for(int j=yl;j<=yr;j++){
		int cnt=0;
		for(int i=xu;i<=xd;i++){
			if(str[i][j]=='r')cnt++;
		}
		if(cnt==xd-xu+1)ym=j;
	}
	memset(sum,0,sizeof(sum));
	for(int i=xu;i<=xm;i++){
		int d=xm-i;
		ul[d]=inf,ur[d]=0;
		for(int j=yl;j<=yr;j++){
			if(str[i][j]=='r'){
				Min(ul[d],j);
				Max(ur[d],j);
			}
		}
		ul[d]=ym-ul[d];
		ur[d]=ur[d]-ym;
	}
	for(int i=xm;i<=xd;i++){
		int d=i-xm;
		dl[d]=inf,dr[d]=0;
		for(int j=yl;j<=yr;j++){
			if(str[i][j]=='r'){
				Min(dl[d],j);
				Max(dr[d],j);
			}
		}
		dl[d]=ym-dl[d];
		dr[d]=dr[d]-ym;
	}
	for(int j=1;j<=n;j++){
		up[0]=dw[n+1]=inf;
		for(int i=1;i<=n;i++){
			if(str[i][j]=='X')up[i]=0;
			else up[i]=up[i-1]+1;
		}
		for(int i=n;i>=1;i--){
			if(str[i][j]=='X')dw[i]=0;
			else dw[i]=dw[i+1]+1;
		}
		for(int i=1;i<=n;i++){
			int L=n,R=1;
			if(up[i]<=xm-xu){
				Min(L,j-ur[up[i]]);
				Max(R,j+ul[up[i]]);
			}
			if(dw[i]<=xd-xm){
				Min(L,j-dr[dw[i]]);
				Max(R,j+dl[dw[i]]);
			}
			Max(L,1),Min(R,n);
			if(L<=R)sum[i][L]++,sum[i][R+1]--;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			sum[i][j]+=sum[i][j-1];
			if(sum[i][j])cov[i][j]=true;
		}
	}
	memset(sum,0,sizeof(sum));
	for(int j=yl;j<=ym;j++){
		int d=ym-j;
		ul[d]=inf,ur[d]=0;
		for(int i=xu;i<=xd;i++){
			if(str[i][j]=='r'){
				Min(ul[d],i);
				Max(ur[d],i);
			}
		}
		ul[d]=xm-ul[d];
		ur[d]=ur[d]-xm;
	}
	for(int j=ym;j<=yr;j++){
		int d=j-ym;
		dl[d]=inf,dr[d]=0;
		for(int i=xu;i<=xd;i++){
			if(str[i][j]=='r'){
				Min(dl[d],i);
				Max(dr[d],i);
			}
		}
		dl[d]=xm-dl[d];
		dr[d]=dr[d]-xm;
	}
	for(int i=1;i<=n;i++){
		up[0]=dw[n+1]=inf;
		for(int j=1;j<=n;j++){
			if(str[i][j]=='X')up[j]=0;
			else up[j]=up[j-1]+1;
		}
		for(int j=n;j>=1;j--){
			if(str[i][j]=='X')dw[j]=0;
			else dw[j]=dw[j+1]+1;
		}
		for(int j=1;j<=n;j++){
			int L=n,R=1;
			if(up[j]<=ym-yl){
				Min(L,i-ur[up[j]]);
				Max(R,i+ul[up[j]]);
			}
			if(dw[j]<=yr-ym){
				Min(L,i-dr[dw[j]]);
				Max(R,i+dl[dw[j]]);
			}
			Max(L,1),Min(R,n);
			if(L<=R)sum[j][L]++,sum[j][R+1]--;
		}
	}
	for(int j=1;j<=n;j++){
		for(int i=1;i<=n;i++){
			sum[j][i]+=sum[j][i-1];
			if(sum[j][i])cov[i][j]=true;
		}
	}
  	//预处理船从四个角出去所花的最少代价
	step11=step1n=stepn1=stepnn=inf;
	for(int i=1;i<=ym-yl;i++){
		Min(step1n,i+ur[i]+1);
		Min(stepnn,i+ul[i]+1);
	}
	for(int i=1;i<=yr-ym;i++){
		Min(stepn1,i+dl[i]+1);
		Min(step11,i+dr[i]+1);
	}
	return BFS();
}
分享到 评论